/**
 * 经典问题，只能向右或者向下走
 * 问从左上到右下的方案总数
 * 
 */
class Solution {

using vi = vector<int>;

vector<vi> D;
int N, M;

public:
    int uniquePaths(int m, int n) {
        N = m;
        M = n;
        D.assign(N + 1, vi(M + 1, -1));     

        D[1][1] = 1;
        for(int i=1;i<=N;++i)for(int j=1;j<=M;++j){
            if(1 == i and 1 == j) continue;
            chkadd(D[i][j], D[i][j - 1]);
            chkadd(D[i][j], D[i - 1][j]);
        }
        return D[N][M];        
    }

    void chkadd(int & d, int a){
        if(-1 == a) return;
        if(-1 == d) return (void)(d = a);
        return (void)(d += a);
    }
};